// function changeNum(num, n = 2) {
//   let stack = [];
//   let number = num;
//   let baseStr = '0123456789ABCDEF'
//   while (number !== 0) {
//     stack.push(number % n)
//     number = Math.floor(number / n)
//   }
//   let str = '';
//   while (stack.length) {
//     str += baseStr[stack.pop()]
//   }
//   console.log(str)
// }
// changeNum(23, 12)




const kuoMap = {
  "(": ")",
  "{": "}",
  "[": "]"
}

function validateStr(str) {
  const stack = [];
  for (let i = 0; i < str.length; i++) {
    const item = str[i];
    if (Object.keys(kuoMap).includes(item)) {
      stack.push(item)
    } else {
      if (kuoMap[stack[stack.length - 1]] === item) {
        stack.pop()
      }
    }
  }
  return !stack.length
}
// console.log(validateStr("([})}"))
// console.log(validateStr("({[]})"))

function game(list, num) {
  const queue = [...list];
  while (queue.length > 1) {
    for (let i = 0; i < num; i++) {
      queue.push(queue.shift())
    }
    console.log('淘汰', queue.shift())

  }
  return queue[0]
}

// console.log(game(['小红', '小城', '小黑', '小蓝', '小绿'], 4))

// value,next -> value1,next1 -> 

// const obj = {
//   value: 1,
//   next: {
//     value: 2,
//     next: {
//       value: 3,
//       next: {
//         value: 4,
//         next: null
//       }
//     }
//   }
// }

class Node {
  constructor(value) {
    this.value = value
    this.next = null
  }
}

// const node = new Node(100)
class LinkList {
  constructor() {
    this.head = null;
    this.count = 0;
  }

  push(value) {
    const node = new Node(value);
    if (this.head) {
      let current = this.head;
      while (current.next) {
        current = current.next
      }
      current.next = node
    } else {
      this.head = node;
    }
    // console.log(this.head)
    this.count++
  }

  removeIndex(index) {
    if (index < 0 || index >= this.count) return;
    let prev;
    let current = this.head;
    if (index === 0) {
      this.head = current.next
    } else {
      for (let i = 0; i < index; i++) {
        prev = current;
        current = current.next
      }
      prev.next = current.next;
    }

    this.count--
  }

  insertIndex(value, index) {
    if (index < 0 || index >= this.count) return
    const node = new Node(value);
    let prev;
    let current = this.head;
    if (index === 0) {
      node.next = current;
      this.head = node;
    } else {
      for (let i = 0; i < index; i++) {
        prev = current;
        current = current.next
      }
      node.next = current
      prev.next = node;
    }

    this.count++
  }
}

// const linkList = new LinkList()
// linkList.push(100)
// linkList.push(200)
// linkList.push(300)
// linkList.push(400)
// linkList.insertIndex(0, 0)
// // linkList.removeIndex(2)

// // 100 -> 200 -> 300 -> 400
// // 100 -> 200 -> 0 -> 300 -> 400


// 排序
const sortArr = [0, 5, 2, 4, 1, 7, 89, 3, 1, 0, 7]

// function swap(arr, i, j) {
//   const temp = arr[i];
//   arr[i] = arr[j];
//   arr[j] = temp
// }

// // ---------------------冒泡排序---------------------------
// function bubbleSort(arr) {
//   // 外层，每次都找最大项
//   for (let i = 0; i < arr.length - 1; i++) {
//     for (let j = 0; j < arr.length - 1 - i; j++) {
//       if (arr[j] > arr[j + 1]) {
//         [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
//       }
//     }
//   }
//   return arr
// }

// console.log('bubbleSort', bubbleSort(sortArr))

// // --------------------选择排序--------------------------------
// function selectSort(arr) {
//   // 1. 外层，找到最小下标，把最小下标和前面的元素做交换
//   // 2. 内层，找最小下标
//   for (let i = 0; i < arr.length - 1; i++) {
//     let minIndex = i;
//     for (let j = i + 1; j < arr.length; j++) {
//       if (arr[minIndex] > arr[j]) {
//         minIndex = j
//       }
//     }
//     if (minIndex !== i) {
//       [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]]
//     }
//   }
//   return arr
// }
// console.log('selectSort', selectSort(sortArr))

// // -----------------------插入排序----------------------------
// // 1. 外层循环从第二项开始，拿当前项与前面的已排的数据做对比
// // 2. 前面数据倒序对比，如果前面数据大于当前项，前面数据后移
// // 3. 如果前面数据小于当前项，将前面数据的位置数据替换为当前项
// function insertSort(arr) {
//   for (let i = 1; i < arr.length; i++) {
//     const temp = arr[i];
//     let j = i;
//     while (j > 0 && arr[j - 1] > temp) {
//       arr[j] = arr[j - 1]
//       j--
//     }
//     arr[j] = temp
//   }
//   return arr
// }
// console.log('insertSort', insertSort(sortArr))

O(nlogn)

// ----------------------快速排序---------------------------
function quickSort(arr) {
  if (arr.length < 2) {
    return arr
  }
  let temp = arr[0];
  let left = arr.slice(1).filter(item => item <= temp)
  let right = arr.slice(1).filter(item => item > temp)
  return quickSort(left).concat(temp, quickSort(right))
}

console.log('quickSort', quickSort(sortArr))






